\chapter{Числа Каталана}

Вот он ночной кошмар любого школьника... Числа Каталана в решении различных задач встречаются не реже чем числа Фибоначчи.

По лекции от 20 октября 2011 года.

\section{Введение}

Наиболее известная задача в которой встречаются числа Каталана - задача о количестве правильных скобочных последовательностей.

\begin{Def}
Правильная скобочная последовательность из $2n$ скобок - это такая последоваетльность, в которой в любом префиксе количество открывающих скобок не меньше количества закрывающих, и кроме того количество открывающих скобок равно количеству закрывающих скобок равно $n$
\end{Def}

Решением этой популярной задачи и являются числа Каталана, но мы рассмотрем более приятную задачу, решением которой так же являются числа Каталана:

пусть на окружности задано $2n$ точек, сколькими способами можно попарно соединить эти точки $n$ отрезками так, чтобы они не пересекались?

Видно, что эта задача эквивалентна задаче о скобках.
Почему? Да все очень просто, две вершины отрезка соответствуют открывающей и закрыающей скобке, и если обходить вершины начиная с некоторой по кругу, то отсутствие пересечений ровное условие на префиксы правильной скобочной последовательности.

Почему мы рассматриваем эту задачу? потому что из геометрических соображений вывести числа Каталана несколько проще. (как мне кажется)

Очевидно что для $n=1$ существует всего один способ, для $n=2$ уже два. Составим рекуррентное соотношение для произвольного $n$. Для начала обозначим наши числа $c_n$. Пусть точки на окружности называются $p_i$. Зафиксируем точку $p_1$. Ее можно соединить только с точками $p_2, p_4, p_6, ... , p_{2i + 2}, ... , p_{2 n - 2}, p_{2 n}$, где $i = \overline{0, n-1}$, почему? Да потому что с каждой стороны от отрезка $p_1 p_{2i+2}$ должно остаться четное число точек, чтобы их можно было соединить отрезками попарно.

Таким образом, если после проведения такого отрезка с одной стороны получили $2 i$ точек, то с другой получим $2 \left(n - i - 1\right)$ точек. Где в левой и правой части опять получаем задачи экваивалентные исходным, но меньшей размерности, в итоге получаем, что для некоторой пары фиксированных точек $p_1$ и $p_{2 i - 2}$ получаем следующее число способов:
\[
	c_{n}^i = c_i c_{n-i-1}
\]
Суммирование по всем возможным $i$ дает требуемое:
\[
	c_{n} = \sum_{i=0}^{n-1} c_{n}^i = \sum_{i=0}^{n-1} c_i c_{n-i-1}
\]
тадам тадам получили что хотели) Решить правдо сие уравнение без извращений не получится) Но на самом деле существует вывод решения приводящий сразу к замкнутой формуле:
\[
	c_{n} = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}
\]

\section{Вкусность}
\[
	\begin{split}
		& \left(1 - \alpha x\right)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} x^k \left(-\alpha\right)^k = \\
		& =  \sum_{k=0}^{\infty} \frac{\left(-n\right)_k}{k!} x^k \left(-\alpha)\right)^k = \\
		& = 1 + \sum_{k=1}^{\infty} \frac{-n \left(-n - 1\right) ... \left(- n - k + 1\right)}{k!} \left(-1\right)^k \alpha^k x^k = \\
		& = 1 + \sum_{k=1}^{\infty} \frac{n\left(n-1\right)...\left(n-k+1\right)}{k!} \left(-1\right)^k \left(-1\right)^k \alpha^k x^k = \\
		& = 1 + \sum_{k=1}^{\infty} \binom{n-k+1}{k} \alpha^k x^k = 1 + \sum_{k=1}^{\infty} \left(\binom{n}{k}\right) \alpha^k x^k = \\
		& = \sum_{k=0} \left(\binom{n}{k}\right) x^k \alpha^k
	\end{split}
\]
получили производящую функцию для последовательностт сочетаний с повторениями.

Другая вкусность нам известна производящая функция для последовательности:
\[
	1, 1, 1, 1, ...
\]
\[
	f\left(x\right) = \frac{1}{1 - x}
\]
Получить последовательность для чисел:
\[
	1, 2, 3, 4, 5 ...
\]
не трудно исходя из соображений, что доможение на $\frac{1}{1-x}$ дает последовательность частичных сумм, итого:
\[
	\frac{1}{\left(1-x\right)^2}
\]
Далее по аналогии для последовательности:
\[
	1, 3, 6, 10, 15, ...
\]
получаем
\[
	\frac{1}{\left(1-x\right)^3}
\]
получем то же самое, но с другой стороны)

\section{Замкнутая формуал для чисел Каталана}

Ну со вкусностями покончено, я вообще не понимаю как они сюда попали, продолжим. Итак для чисел Каталана справедлива формула:

\[
	c_{n+1} = c_0 c_{n} + c_1 c_{n-1} + c_2 c_{n-2} + ... + c_{n-1} c_1 + c_n c_0
\]

не трудно увидеть, что оно похоже на произведение обыкновенных производящих функций, ну так и поступим, составим производящую функцию для чисел Кталана:
\[
	f\left(x\right) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + ...
\]
Домножим рекуррентное соотношение на $x^{n+1}$ и просуммируем по всем $n$:
\[
	\begin{split}
		& \sum_{n=0}^{\infty} c_{n+1} x^{n+1} = \sum_{n=0}^{\infty} \left[\sum_{k=0}^{n} c_k c_{n-k}\right] x^{n+1} \Leftrightarrow \\
		& \Leftrightarrow f\left(x\right) - c_0 = x f\left(x\right) f\left(x\right) \\
		& f\left(x\right) = \frac{1 \pm \sqrt{1-4x}}{2x}
	\end{split}
\]
ну теперь играем в угадайку, и угадываем, что правильный знак $-$, вообщем есть и формальное обосновнаие, но оно неинтересное и вообще страшное... так что пусть мы угадали:
\[
	\begin{split}
		& f\left(x\right) = \frac{1}{2x} \left(1 - \left(1 - 4x\right)^{-\frac{1}{2}}\right) = \\
		& = \frac{1}{2x} \left(1 - 1 - \sum_{n=1}^{\infty} \frac{\frac{1}{2} \left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right) ... \left(\frac{1}{2}-n+1\right)}{n!} \left(-4x\right)^n\right) = \\
		& = \frac{1}{2x} \sum_{n=1}^{\infty} \frac{\frac{1}{2} \frac{1}{2} \frac{3}{2} \frac{5}{2} ... \left(n-\frac{3}{2}\right)}{n!} 2^{2n} x^n = \frac{1}{2x}\sum_{n=1}^{\infty}\frac{1 \cdot 3 \cdot 5 \cdot ... \cdot \left(2n-3\right)}{n!} 2^n x^n = \\
		& = \sum_{n=1}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdot ... \cdot \left(2n-3\right)}{n!} 2^{n-1} x^{n-1} = \\
		& = \sum_{n=1}^{\infty} \frac{\left(n-1\right)! 1 \cdot 3 \cdot 5 \cdot ... \cdot \left(2n-3\right)}{n!\left(n-1\right)!} 2^{n-1}x^{n-1} = \\
		& = \sum_{n=1}^{\infty} \frac{2 \cdot 4 \cdot 6 \cdot ... \cdot \left(2n-2\right) \cdot 1 \cdot 3 \cdot 5 \cdot ... \cdot \left(2n-3\right)}{n \left(\left(n-1\right)!\right)^2} x^{n-1} = \\
		& = \sum_{n=1}^{\infty} \frac{\left(2n-2\right)!}{n \left(n-1\right)! \left(n-1\right)!} x^{n-1} = \sum_{n=0}^{\infty} \frac{2n!}{\left(n+1\right) n! n!} x^n = \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n} x^n
	\end{split}
\]
выбераем из производящей функции нужное значение:
\[
	c_n = \frac{1}{n+1} \binom{2n}{n}
\]
